/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-16 10:36:52
 * @LastEditors: lily
 * @LastEditTime: 2021-04-16 11:31:56
 */
/*
 * @lc app=leetcode.cn id=49 lang=javascript
 *
 * [49] 字母异位词分组
 */

// @lc code=start
/**
 * @param {string[]} strs
 * @return {string[][]}
 */

//  思路：
//  不论通过计数还是排序，将不同顺序内容相同的str生成同一key加入map
//  判断新str只要判断其生成的key是否已存在于map

//  复杂度：
//  排序法：O(nklogk)  O(nk)  n为strs长度，k为strs中字符串最大长度
//  计数法：O(n(k+∣Σ∣))  O(n(k+∣Σ∣))    ∣Σ∣为26

var groupAnagrams = function (strs) {
    // 排序法
    let map = new Map();
    strs.forEach((str) => {
        // str由类数组转换为数组进行排序后再转换回来
        // 保证不同顺序的str拥有相同的key
        let key = Array.from(str).sort().toString();
        // map是否有key，有则加入数组，没有创建新数组加入map
        map.has(key) ? map.get(key).push(str) : map.set(key, [str]);
    });
    // 将map的值转化为数组
    return Array.from(map.values());

    // 计数法
    // const map = new Object();
    // for (let s of strs) {
    //     const count = new Array(26).fill(0);
    //     for (let c of s) {
    //         count[c.charCodeAt() - 'a'.charCodeAt()]++;
    //     }
    //     map[count] ? map[count].push(s) : map[count] = [s];
    // }
    // return Object.values(map);
};
// @lc code=end



